% !Mode:: "TeX:UTF-8"
\addcontentsline{toc}{chapter}{Введение}
\chapter*{Введение}

\section*{Актуальность}
%А) микропроцессоры сложные -> в них есть ошибки
Современные микропроцессоры --- это сложные системы, поэтому вероятность появления ошибки как при проектировании микропроцессора, так и при его производстве становится всё выше. При этом <<цена ошибки>> в готовом микропроцессоре велика (как минимум, это означает перевыпуск микропроцессора заново). Поэтому актуально развитие методов верификации микропроцессоров.

Вероятность ошибки выше там, где выше сложность. К числу наиболее сложных механизмов современных процессоров, использующих конвейеры и многоуровневые буфера типа кэш-памяти, относится механизм доступа к памяти.
%по этой причине в качестве темы диссертации была выбрана тема тестирования ПОДСИСТЕМ УПРАВЛЕНИЯ ПАМЯТИ.


%Б) история вопроса

%В) основная доля ошибок на этапе разработки моделей (design'а)
Современные технологии проектирования микропроцессоров представляют собой средства разработки \emph{модели (design) на специальных языках} типа VHDL или Verilog~\cite{VerilogDesign}. Эти технологии позволяют в конечном итоге построить так называемые <<синтезируемые модели>>, из которых автоматически получаются фотошаблоны, необходимые для производства. Основная доля ошибок появляется именно на этапе разработки моделей (design), поэтому основные усилия по их выявлению или даже предотвращению их появления, также приходятся на фазу разработки моделей. Поэтому данная работа также нацелена на выявление ошибок в моделях микропроцессоров.

%Г) модульное и системное тестирование ->
% интересные ситуации нельзя создать инструкциями
Тестирование на модели бывает \emph{модульным} (unit-level verification) и \emph{системным} (core-level verification, full-chip level verification)~\cite{UnitCoreLevel}. Модульное тестирование модели микропроцессора предполагает генерацию тестовых воздействий на входы отдельных модулей, блоков, микропроцессора, описанных на одном из языков типа VHDL, Verilog, и проверку выходов таких блоков. В рамках системного тестирования проверяется работа всего микропроцессора в целом --- тестом здесь является некоторая тестовая программа (программа на машинном языке), которая загружается в память и выполняется микропроцессором (речь все время идет о некоторой программной модели микропроцессора). Поскольку размер и сложность отдельного блока всегда меньше, размера и сложности микропроцессора в целом, потенциально качество модульного тестирования может быть выше, чем системного. Однако для достижения высокого качества тестирования как число модульных тестов, так и совокупная трудоемкость их изготовления, являются очень большими. Это вынуждает часть проверок проводить на модульном уровне, а другую часть на системном.

Сложность микропроцессора определяет количество системных тестов. Если выделить различные аспекты функционирования микропроцессора (конвейер, буферы подсистемы управления памяти), то особое функционирование возникает при различных комбинациях этих аспектов. Это означает, что количество тестов должно быть не меньше произведения количества разных аспектов. Количество инструкций измеряется сотнями, а цепочек инструкций, соответственно, порядками сотен, плюс если учесть возможные аспекты в конвейере, в кэш-памяти, количество тестов получается очень большим. Для избежания проблемы такого <<взрывного>> характера количества тестов, их объединяют в классы эквивалентности --- \emph{тестовые ситуации}.

При этом есть проблема покрытия всех потенциально интересных тестовых ситуаций. Нет никаких прямых способов создать многие из таких ситуаций нет. Например, интересно, как происходит доступ в память, когда соответствующий адрес имеется в кэш-памяти или не имеется. Или еще более тонкий анализ --- адрес имеется/или не имеется в кэш-памяти второго уровня. Среди инструкций процессора нет таких, которые были бы предназначены специально для создания таких ситуаций. Эти ситуации создаются \emph{динамически} в ходе выполнения программ.


%Д) схема системного тестирования, показать здесь смежные вопросы
% (вопросы построения оракула, покрытия и др.)
Рассмотрим традиционную схему системного тестирования, известные подходы к автоматизации построения тестов и выявим проблемы, которые мешают строить более эффективные тесты.

Микропроцессор рассматривается как черный (или серый) ящик. Входными тестовыми данными является некоторая программа, которая загружается в память. Результатом прогона теста является либо финальное состояние памяти (возможно, включая состояние регистров) или (в случае <<серого ящика>>) трасса изменения значений ячеек памяти или регистров.
В этой общей схеме тестирования пока не упомянуты:
\begin{itemize}
	\item	генератор тестов (или набор уже готовых тестов);
	\item	подсистема проверки корректности полученного результата --- тестового оракула, или арбитра;
	\item	перечень <<интересных>> ситуаций, которые надо воспроизвести в ходе выполнения тестов;
	\item	некая система мониторинга, которая фиксирует прохождение <<интересных>> ситуаций --- оценивает полноту покрытия.
\end{itemize}

Тестовый оракул, или арбитр, строится по схеме с использованием <<эталонной>> модели (simulation-based verification)~\cite{SimulationBased}. Каждая тестовая программа выполняется на двух моделях --- на тестируемой (design) и на <<эталонной>>. Потом состояния памяти или трассы изменения состояния памяти для тестируемой и эталонной моделей сравниваются. Если оракул признает, что трассы не эквивалентны, это свидетельствует о наличии ошибки в тестируемой системе (или эталонной, но это происходит реже). Как правило, эталонная модель пишется на одном из языков программирования (например, Си или Си++) и не загромождается деталями.  На этом основании считается, что такая модель существенно проще тестируемой, в ней с меньшей вероятностью встречаются ошибки, именно поэтому к ней можно относиться как к <<эталонной>>.

% критика этого подхода: он не позволяет проверить модули, работающие за счет внешних воздействий - For example, fast interrupt request (FIQ), interrupt request (IRQ), data abort exception (Dabort) and prefetch abort exception (Pabort) of ARM7. Это пишут в статье "Automatic Verification of External Interrupt Behaviors for Microprocessor Design", авторы Fu-Ching Yang, Wen-Kai Huang, Ing-Jer Huang.


Методы автоматической генерации тестов делят на псевдослучайные/комбинаторные (pseudo-random) и целенаправленные (что не отменяет возможности использования уже готовых тестов)~\cite{HoPhD}. В случае псевдослучайной генерации инструкции, их порядок и аргументы выбираются случайным образом или перебираются некоторым комбинаторным способом. Целенаправленная генерация начинается с задания некоторого шаблона тестовой программы, который определяет набор инструкций, их последовательность и аргументы. В рамках целенаправленной генерации порядок инструкций и их аргументы должны быть подобраны таким образом, чтобы каждый новый тест покрывал новые, еще не покрытые тестовые ситуации. Целенаправленную генерацию можно реализовать как выполнение массовой генерации комбинаторных тестов с последующей фильтрацией, с тем чтобы оставлять только те тесты, которые дают дополнительное покрытие. Однако уже для достаточно коротких шаблонов (длиной 3-4 инструкции) перебор становится слишком большим.

Целенаправленная генерация тестов дает по тесту на каждую ситуацию. Набор тестов, которые покрывают все ситуации, называют нацеленными тестами (нацеленными на эти ситуации). Набор ситуаций конечен, следовательно и набор нацеленных тестов конечен. Вопрос
%(это и есть основная тема исследования)
, как систематическим образом строить тестовые программы, чтобы в совокупности они воспроизвели все заданные <<интересные>> ситуации.


Перечень (конечный) <<интересных>> ситуаций и мониторинг. В совокупности две эти возможности задают метрику и механизм оценки полноты тестирования. Мониторинг организовать относительно легко, поскольку мы работаем не с реальным процессором, а с его моделями. Как построить перечень «интересных» ситуаций» --- вопрос открытый --- это одно из направлений моей работы.

%Е) нацеленное/ненацеленное тестирование

\section*{Цель работы}
%Ж) формулирование цели работы - исследование методов построения нацеленных тестов-программ (на память)
%Целью исследования является разработка методов целенаправленной генерации системных тестов, которые, в свою очередь, должны предлагать и адекватные методы задания метрики и оценки полноты покрытия в соответствии с предложенными метриками.

Целью диссертационной работы является разработка методов целенаправленной генерации системных тестов. Методы должны предполагать адекватные метрики покрытия.

Для достижения этой цели были поставлены следующие задачи:
\begin{enumerate}
	\item проанализировать описанные в научной литературе методы целенаправленной генерации системных тестов;
	\item выделить среди них методы и подходы, дающие возможность генерации тестов для реальных подсистем управления памяти;
	\item предложить методы целенаправленной генерации системных тестов для подсистем управления памяти, если таких методов нет.
\end{enumerate}
